/**************************************************************
          File Name:quick_sort.c
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: 2015-04-14 12:09:35
***************************************************************/

#include<stdio.h>

int random_generator(int s, int e)
{
    int res;
    res = e%309;
    return res < 0 ? 0-res : res;
}

int exchange(int A[], int start, int end)
{
    int i, j, tmp;
    
    i = start - 1;

    for(j = start; j <= end - 1; j++)
    {
        if(A[j] <= A[end])      // A[end] is the pivot 
        {
            i++;
            tmp = A[j];
            A[j] = A[i];
            A[i] = tmp;
        }
    }
    tmp = A[i+1];
    A[i+1] = A[end];
    A[end] = tmp;
    return i+1;             // return pivot index after exchanging
}

int random_exc(int A[], int start, int end)
{
    int pivot, tmp;
    pivot = random_generator(start, end);
    tmp = A[pivot];
    A[pivot] = A[end];
    A[end] = tmp;
    return exchange(A, start, end);
}

void quick_sort(int A[], int start, int end)
{
    int sep;
    if(start < end)
    {
        //sep = exchange(A, start, end);
        sep = random_exc(A, start, end);        // better expectation
        quick_sort(A, start, sep - 1);
        quick_sort(A, sep + 1, end);
    }
}

int main(int argc, char *argv[])
{
    int i, A[] = {9,1,309,92,89, 1992, 1989};
    int size = sizeof(A) / sizeof(A[0]);
    quick_sort(A, 0, size);
    for(i=0; i<size; i++)
        printf("%d\t", A[i]);
    putchar('\n');
    return 0;
}
